package com.ocean.tree;

import java.util.*;

/**
 * <Description> <br>
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/09 <br>
 */
public class BinaryTreeSearchTree {
    private TreeNode tree;

    public BinaryTreeSearchTree() {
    }

    /**
     *          6
     *      4        9
     *    3   5   8     11
     *  2
     *
     * @param args
     */
    public static void main(String[] args) {
        BinaryTreeSearchTree tree = new BinaryTreeSearchTree();
        tree.insert(6);
        tree.insert(4);
        tree.insert(9);
        tree.insert(11);
        tree.insert(3);
        tree.insert(2);
        tree.insert(5);
        tree.insert(8);
        List<Integer> res = tree.print();
        System.out.println(res);
    }

    public void insert(int data) {
        if (tree == null) {
            tree = new TreeNode(data);
            return;
        }
        // 找到要插入的位置
        TreeNode p = tree;
        while (p != null) {
            int curVal = p.getValue();
            if (data > curVal) {
                if (p.getRight() == null) {
                    p.setRight(new TreeNode(data));
                    return;
                }
                p = p.getRight();
            } else {
                if (p.getLeft() == null) {
                    p.setLeft(new TreeNode(data));
                    return;
                }
                p = p.getLeft();
            }
        }

    }

    public TreeNode find(int data) {
        TreeNode p = tree;
        while (p != null && p.getValue() != data) {
            if (p.getValue() == data) {
                return p;
            }
            if (data > p.getValue()) {
                p = p.getRight();
            } else {
                p = p.getLeft();
            }
        }
        return null;
    }

    public void delete(int data) {
        // 找到这个节点 并将其父节点记录下来
        TreeNode p = tree;
        // 记录父节点
        TreeNode pp = null;
        while (p != null && p.getValue() != data) {
            pp = p;
            if (p.getValue() > data) {
                p = p.getLeft();
            } else {
                p = p.getRight();
            }
        }
        if (p == null) {
            return; // 没有找到
        }
        // p有左右两个字节点的情况
        if (p.getLeft() != null && p.getRight() != null) {
            // 到右边找到最小的左节点 替换到当前位置
            TreeNode minP = p.getRight(); // 向右边找
            TreeNode minPP = pp;
            while (minP.getLeft() != null) {
                minPP = minP;
                minP = minP.getLeft();
            }
            // 找到叶子节点了 就讲叶子节点的值替换到要删除的位置
            p.setValue(minP.getValue());
            pp = minPP; // 转变成要删除最小节点
            p = minP;
        }

        TreeNode child;
        // 找到子节点
        if (p.getLeft() != null) {
            child = p.getLeft();
        } else if (p.getRight() != null) {
            child = p.getRight();
        } else {
            child = null; // 说明要删除的是子节点
        }
        // 执行真正的删除 就是将该节点用null替换 该节点的父节点要指向他的子节点
        // 父节点为空 说明要删除根节点
        if (pp == null) {
            tree = child;
        } else if (pp.getLeft() == p) {
            // 删的是左节点
            pp.setLeft(child);
        } else {
            // 删右节点
            pp.setRight(child);
        }
    }

    /**
     *          6
     *      4        9
     *    3   5   8     11
     *  2
     *
     * @param args
     */
    public List<Integer> print() {
        if (tree == null) {
            return Collections.emptyList();
        }
        // 中序遍历
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode p = tree;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.getLeft();
            }
            // 左边为空了 就出栈
            p = stack.pop();
            // 放到集合中
            res.add(p.getValue());
            p = p.getRight();
        }
        return res;
    }
}
